Complexity of log-concave inequalities in matroids

Abstract: A sequence of nonnegative real numbers a_1, a_2, ..., a_n, is log-concave if a_i^2 <= a_{i-1} a_{i+1} for all i ranging from 2 to n-1. Examples of log-concave inequalities range from inequalities that are readily provable, such as the binomial coefficients a_i = \binom{n}{i}, to intricate inequalities that have taken decades to resolve, such as the number of independent sets a_i in a matroid M with i elements (otherwise known as the first Mason's conjecture; and was resolved by June Huh in 2010s in a remarkable breakthrough). It is then natural to ask if it can be shown that the latter type of inequalities is intrinsically more challenging than the former. In this talk, we provide a rigorous framework to answer this type of questions, by employing a combination of combinatorics, complexity theory, and geometry. This is a joint work with Igor Pak.

algebraic geometrycombinatorics

Audience: researchers in the discipline

MAAGC 2024

Series comments: The 2024 annual Mid-Atlantic Algebra, Geometry, and Combinatorics (MAAGC) Workshop will take place Friday and Saturday, October 11-12, 2024 at The George Washington University in Washington, DC.

The MAAGC Workshop aims to bring together senior researchers and junior mathematicians from the region to exchange ideas and forge collaborations in algebra, geometry, and combinatorics. The conference is funded by National Science Foundation grant DMS-2408985.